//当面试官要求你实现一个排序算法，时间复杂度为O(n)时
//你应该问清楚要排序的数是否在一定范围内
//并且问清楚要排序的数字数量的多少
//问清楚是否可以申请辅助空间


//当面试官要求你对他们公司的员工年龄进行排序，他们公司大概有几万名员工，而且可以用到辅助空间
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

//既然是对年龄进行排序，年龄肯定是在一个小范围中的，我们取这里的年龄范围为1-99,
//用一个数组来存放年龄出现的次数
#define  Maxage 100
void my_sort(size_t  ages[],size_t  length)
{
    assert(ages);
    if(length<=1)
    {
        return;
    }
    int timesOfAge[Maxage]={0};
    size_t i=0;
    for(i=0;i<length;++i)
    {
        assert(ages[i]>0&&ages[i]<Maxage);//年龄不在合法范围内
        ++timesOfAge[ages[i]];
    }
    //这样就将所有员工的年龄遍历一遍后，将每个年龄出现的次数统计出来
    //接下来就遍历timesOfAge[99],下标就代表年龄，数组元素就代表员工数量。
    //从下标为1开始遍历
    size_t index=0;
    for(i=1;i<Maxage;++i)
    {
        while(timesOfAge[i]--!=0)
        {
            ages[index++]=i;
        }
    }
}
void Print(size_t ages[],size_t length)
{
    assert(ages);
    if(length<=0)
    {
        return;
    }
    size_t i=0;
    for(i=0;i<length;++i)
    {
        printf("%lu ",ages[i]);
    }
    printf("\n");
}
int main()
{
    //size_t  ages[]={44,78,67,56,34,23};
    //size_t  ages[]={44,100,78,67,56,34,23};
    size_t *ages=NULL;
    size_t length=sizeof(ages)/sizeof(ages[0]);
    //size_t length=0;
    Print(ages,length);
    my_sort(ages,length);
    Print(ages,length);
    return 0;
}

